package binPack.maxRect
{
	import flash.geom.Rectangle;

	/**
	 * 
	 *Implements different bin packer algorithms that use the MAXRECTS data structure.
	 *This work is released to Public Domain, do whatever you want with it.
	 * @see https://github.com/juj/RectangleBinPack/blob/master/MaxRectsBinPack.cpp
	 * @author Jukka Jylänki
	 * @revised adodo08
	 */
	public class MaxRectsBinPack
	{
		public var binWidth:int;
		public var binHeight:int;
		private var usedRectangles:Vector.<Rectangle>;
		private var freeRectangles:Vector.<Rectangle>;
		public function MaxRectsBinPack(width:int=0, height:int=0)
		{
			this.Init(width, height);
		}
		
		public function Init(w:int, h:int):void{
			this.binWidth = w;
			this.binHeight = h;
			this.usedRectangles = new Vector.<Rectangle>();
			this.freeRectangles = new Vector.<Rectangle>();
			var r:Rectangle = new Rectangle(0,0,w,h);
			this.freeRectangles.push(r);
		}
		/**
		 *  Inserts the given list of rectangles in an offline/batch mode, possibly rotated.
		 * @param rects	The list of rectangles to insert. This vector will be destroyed in the process.
		 * @param dst	[out] This list will contain the packed rectangles. The indices will not correspond to that of rects.
		 * @param method	The rectangle placement rule to use when packing.
		 * @see FreeRectChoiceHeuristic
		 */		
		public function InsertRects(rects:Vector.<Rectangle>, dst:Vector.<Rectangle>, method:int):void{
//			dst.clear();
			
			while(rects.length > 0)
			{
				var bestScore1:int = int.MAX_VALUE;
				var bestScore2:int = int.MAX_VALUE;
				var bestRectIndex:int = -1;
				var bestNode:Rectangle;
				
				for(var i:int = 0; i < rects.length; ++i)
				{
					var score1:int = 0;
					var score2:int = 0;
					var result:Object = ScoreRect(rects[i].width, rects[i].height, method, score1, score2);
					var newNode:Rectangle = result.node;
					score1 = result.score1;
					score2 = result.score2;
					
					if (score1 < bestScore1 || (score1 == bestScore1 && score2 < bestScore2))
					{
						bestScore1 = score1;
						bestScore2 = score2;
						bestNode = newNode;
						bestRectIndex = i;
					}
				}
				
				if (bestRectIndex == -1)
					return;
				
				PlaceRect(bestNode);
				rects.splice( bestRectIndex, 1);
			}
		}
		
		/**
		 * Inserts a single rectangle into the bin, possibly rotated.
		 * @param w width
		 * @param h	height
		 * @param method 
		 * @see FreeRectChoiceHeuristic
		 * @return Rectangle
		 * 
		 * 
		 */		
		public function Insert(w:int, h:int,method:int):Rectangle{
			var newNode:Rectangle;
			var score1:int = int.MAX_VALUE;
			var score2:int = int.MAX_VALUE;
			switch( method ){
				case FreeRectChoiceHeuristic.RectBestShortSideFit:
					var result:Object = FindPositionForNewNodeBestShortSideFit(w,h,score1,score2);
					newNode = result.node;
					score1 = result.score1;
					score2 = result.score2;
					break;
				case FreeRectChoiceHeuristic.RectBottomLeftRule:
					result = FindPositionForNewNodeBottomLeft(w,h,score1,score2);
					newNode = result.node;
					score1 = result.score1;
					score2 = result.score2;
					break;
				case FreeRectChoiceHeuristic.RectContactPointRule:
					result = FindPositionForNewNodeContactPoint(w,h,score1);
					newNode = result.node;
					score1 = result.score1;
					break;
				case FreeRectChoiceHeuristic.RectBestLongSideFit:
					result = FindPositionForNewNodeBestLongSideFit(w,h,score2,score1);
					newNode = result.node;
					score1 = result.score1;
					score2 = result.score2;
					break;
				case FreeRectChoiceHeuristic.RectBestAreaFit:
					result = FindPositionForNewNodeBestAreaFit(w,h,score1,score2);
					newNode = result.node;
					score1 = result.score1;
					score2 = result.score2;
					break;
			}
			
			if( newNode.height == 0)
				return newNode;
			
			var len:int = this.freeRectangles.length; 
			for(var i:int = 0; i < len; ++i)
			{
				if (SplitFreeNode(freeRectangles[i], newNode))
				{
					freeRectangles.splice(i,1);
					--i;
					--len;
				}
			}
			
			PruneFreeList();
			
			usedRectangles.push(newNode);
			return newNode;
		}
		/**
		 * Computes the ratio of used surface area to the total bin area.
		 * */
		public function Occupancy():Number{
			var usedSurfaceArea:Number = 0;
			for(var i:int = 0; i < usedRectangles.length; ++i)
				usedSurfaceArea += usedRectangles[i].width * usedRectangles[i].height;
			
			return usedSurfaceArea / (binWidth * binHeight);
		}
		/**
		 *	Computes the placement score for placing the given rectangle with the given method. 
		 * @param width
		 * @param height
		 * @param method
		 * @param score1 [out] The primary placement score will be outputted here.
		 * @param score2 [out] The secondary placement score will be outputted here. This isu sed to break ties.
		 * @return This struct identifies where the rectangle would be placed if it were placed.
		 * 
		 */		
		private function ScoreRect(width:int, height:int, method:int, score1:int, score2:int):Object{
			var newNode:Rectangle;
			var score1:int = int.MAX_VALUE;
			var score2:int = int.MAX_VALUE;
			var result:Object;
			switch(method)
			{
				case FreeRectChoiceHeuristic.RectBestShortSideFit: 
					result = FindPositionForNewNodeBestShortSideFit(width, height, score1, score2); 
					newNode = result.node;
					score1 = result.score1;
					score2 = result.score2;
					break;
				case FreeRectChoiceHeuristic.RectBottomLeftRule: 
					result = FindPositionForNewNodeBottomLeft(width, height, score1, score2); 
					newNode = result.node;
					score1 = result.score1;
					score2 = result.score2;
					break;
				case FreeRectChoiceHeuristic.RectContactPointRule: 
					result = FindPositionForNewNodeContactPoint(width, height, score1); 
					newNode = result.node;
					score1 = result.score1;
					score1 = -score1; // Reverse since we are minimizing, but for contact point score bigger is better.
					break;
				case FreeRectChoiceHeuristic.RectBestLongSideFit: 
					result = FindPositionForNewNodeBestLongSideFit(width, height, score2, score1); 
					newNode = result.node;
					score1 = result.score1;
					score2 = result.score2;
					break;
				case FreeRectChoiceHeuristic.RectBestAreaFit: 
					result = FindPositionForNewNodeBestAreaFit(width, height, score1, score2); 
					newNode = result.node;
					score1 = result.score1;
					score2 = result.score2;
					break;
			}
			
			// Cannot fit the current rectangle.
			if (newNode.height == 0)
			{
				score1 = int.MAX_VALUE;
				score2 = int.MAX_VALUE;
			}
			
			return {node:newNode, score1:score1, score2:score2};
		}
	
		/**
		 * Places the given rectangle into the bin. 
		 * @param node
		 * 
		 */		
		private function PlaceRect(node:Rectangle):void{
			var numRectanglesToProcess:int = freeRectangles.length;
			for(var i:int = 0; i < numRectanglesToProcess; ++i)
			{
				if (SplitFreeNode(freeRectangles[i], node))
				{
					freeRectangles.splice( i, 1);
					--i;
					--numRectanglesToProcess;
				}
			}
			
			PruneFreeList();
			
			usedRectangles.push(node);
		}
		/**
		 * Computes the placement score for the -CP variant. 
		 * @param x
		 * @param y
		 * @param width
		 * @param height
		 * @return 
		 * 
		 */		
		private function ContactPointScoreNode(x:int, y:int, width:int, height:int):int{
			var score:int = 0;
			
			if (x == 0 || x + width == binWidth)
				score += height;
			if (y == 0 || y + height == binHeight)
				score += width;
			
			for(var i:int = 0; i < usedRectangles.length; ++i)
			{
				if (usedRectangles[i].x == x + width || usedRectangles[i].x + usedRectangles[i].width == x)
					score += CommonIntervalLength(usedRectangles[i].y, usedRectangles[i].y + usedRectangles[i].height, y, y + height);
				if (usedRectangles[i].y == y + height || usedRectangles[i].y + usedRectangles[i].height == y)
					score += CommonIntervalLength(usedRectangles[i].x, usedRectangles[i].x + usedRectangles[i].width, x, x + width);
			}
			return score;
		}
		
		private function FindPositionForNewNodeBottomLeft(width:int, height:int, bestY:int, bestX:int):Rectangle{
			var bestNode:Rectangle;
			
			var bestY:int = int.MAX_VALUE;
			var bestX:int = int.MAX_VALUE;
			
			for(var i:int = 0; i < freeRectangles.length; ++i)
			{
				// Try to place the rectangle in upright (non-flipped) orientation.
				if (freeRectangles[i].width >= width && freeRectangles[i].height >= height)
				{
					var topSideY:int = freeRectangles[i].y + height;
					if (topSideY < bestY || (topSideY == bestY && freeRectangles[i].x < bestX))
					{
						bestNode.x = freeRectangles[i].x;
						bestNode.y = freeRectangles[i].y;
						bestNode.width = width;
						bestNode.height = height;
						bestY = topSideY;
						bestX = freeRectangles[i].x;
					}
				}
				if (freeRectangles[i].width >= height && freeRectangles[i].height >= width)
				{
					var topSideY:int = freeRectangles[i].y + width;
					if (topSideY < bestY || (topSideY == bestY && freeRectangles[i].x < bestX))
					{
						bestNode.x = freeRectangles[i].x;
						bestNode.y = freeRectangles[i].y;
						bestNode.width = height;
						bestNode.height = width;
						bestY = topSideY;
						bestX = freeRectangles[i].x;
					}
				}
			}
			return bestNode;
		}
		
		private function FindPositionForNewNodeBestShortSideFit(width:int, height:int, bestShortSideFit:int, bestLongSideFit:int):Object{
			var bestNode:Rectangle = new Rectangle();
			
			bestShortSideFit = int.MAX_VALUE;
			bestLongSideFit = int.MAX_VALUE;
			
			for(var i:int = 0; i < freeRectangles.length; ++i)
			{
				// Try to place the rectangle in upright (non-flipped) orientation.
				if (freeRectangles[i].width >= width && freeRectangles[i].height >= height)
				{
					var leftoverHoriz:int = Math.abs(freeRectangles[i].width - width);
					var leftoverVert:int = Math.abs(freeRectangles[i].height - height);
					var shortSideFit:int = Math.min(leftoverHoriz, leftoverVert);
					var longSideFit:int = Math.max(leftoverHoriz, leftoverVert);
					
					if (shortSideFit < bestShortSideFit || (shortSideFit == bestShortSideFit && longSideFit < bestLongSideFit))
					{
						bestNode.x = freeRectangles[i].x;
						bestNode.y = freeRectangles[i].y;
						bestNode.width = width;
						bestNode.height = height;
						bestShortSideFit = shortSideFit;
						bestLongSideFit = longSideFit;
					}
				}
				
				if (freeRectangles[i].width >= height && freeRectangles[i].height >= width)
				{
					var flippedLeftoverHoriz:int = Math.abs(freeRectangles[i].width - height);
					var flippedLeftoverVert:int = Math.abs(freeRectangles[i].height - width);
					var flippedShortSideFit:int = Math.min(flippedLeftoverHoriz, flippedLeftoverVert);
					var flippedLongSideFit:int = Math.max(flippedLeftoverHoriz, flippedLeftoverVert);
					
					if (flippedShortSideFit < bestShortSideFit || (flippedShortSideFit == bestShortSideFit && flippedLongSideFit < bestLongSideFit))
					{
						bestNode.x = freeRectangles[i].x;
						bestNode.y = freeRectangles[i].y;
						bestNode.width = height;
						bestNode.height = width;
						bestShortSideFit = flippedShortSideFit;
						bestLongSideFit = flippedLongSideFit;
					}
				}
			}
			return {node:bestNode,score1:bestShortSideFit,score12:bestLongSideFit};
		}
		
		private function FindPositionForNewNodeBestLongSideFit(width:int, height:int, bestShortSideFit:int, bestLongSideFit:int):Object{
			var bestNode:Rectangle;
			
			bestShortSideFit = int.MAX_VALUE;
			bestLongSideFit = int.MAX_VALUE;
			
			for(var i:int = 0; i < freeRectangles.length; ++i)
			{
				// Try to place the rectangle in upright (non-flipped) orientation.
				if (freeRectangles[i].width >= width && freeRectangles[i].height >= height)
				{
					var leftoverHoriz:int = Math.abs(freeRectangles[i].width - width);
					var leftoverVert:int = Math.abs(freeRectangles[i].height - height);
					var shortSideFit:int = Math.min(leftoverHoriz, leftoverVert);
					var longSideFit:int = Math.max(leftoverHoriz, leftoverVert);
					
					if (longSideFit < bestLongSideFit || (longSideFit == bestLongSideFit && shortSideFit < bestShortSideFit))
					{
						bestNode.x = freeRectangles[i].x;
						bestNode.y = freeRectangles[i].y;
						bestNode.width = width;
						bestNode.height = height;
						bestShortSideFit = shortSideFit;
						bestLongSideFit = longSideFit;
					}
				}
				
				if (freeRectangles[i].width >= height && freeRectangles[i].height >= width)
				{
					var leftoverHoriz:int = Math.abs(freeRectangles[i].width - height);
					var leftoverVert:int = Math.abs(freeRectangles[i].height - width);
					var shortSideFit:int = Math.min(leftoverHoriz, leftoverVert);
					var longSideFit:int = Math.max(leftoverHoriz, leftoverVert);
					
					if (longSideFit < bestLongSideFit || (longSideFit == bestLongSideFit && shortSideFit < bestShortSideFit))
					{
						bestNode.x = freeRectangles[i].x;
						bestNode.y = freeRectangles[i].y;
						bestNode.width = height;
						bestNode.height = width;
						bestShortSideFit = shortSideFit;
						bestLongSideFit = longSideFit;
					}
				}
			}
			return {node:bestNode, score1:bestShortSideFit , score2:bestLongSideFit };
		}
			
		private function FindPositionForNewNodeBestAreaFit(width:int, height:int, bestAreaFit:int, bestShortSideFit:int):Object {
			var bestNode:Rectangle;
			
			bestAreaFit = int.MAX_VALUE;
			bestShortSideFit = int.MAX_VALUE;
			
			for(var i:int = 0; i < freeRectangles.length; ++i)
			{
				var areaFit:int= freeRectangles[i].width * freeRectangles[i].height - width * height;
				
				// Try to place the rectangle in upright (non-flipped) orientation.
				if (freeRectangles[i].width >= width && freeRectangles[i].height >= height)
				{
					var leftoverHoriz:int = Math.abs(freeRectangles[i].width - width);
					var leftoverVert:int = Math.abs(freeRectangles[i].height - height);
					var shortSideFit:int = Math.min(leftoverHoriz, leftoverVert);
					
					if (areaFit < bestAreaFit || (areaFit == bestAreaFit && shortSideFit < bestShortSideFit))
					{
						bestNode.x = freeRectangles[i].x;
						bestNode.y = freeRectangles[i].y;
						bestNode.width = width;
						bestNode.height = height;
						bestShortSideFit = shortSideFit;
						bestAreaFit = areaFit;
					}
				}
				
				if (freeRectangles[i].width >= height && freeRectangles[i].height >= width)
				{
					var leftoverHoriz:int = Math.abs(freeRectangles[i].width - height);
					var leftoverVert:int = Math.abs(freeRectangles[i].height - width);
					var shortSideFit:int = Math.min(leftoverHoriz, leftoverVert);
					
					if (areaFit < bestAreaFit || (areaFit == bestAreaFit && shortSideFit < bestShortSideFit))
					{
						bestNode.x = freeRectangles[i].x;
						bestNode.y = freeRectangles[i].y;
						bestNode.width = height;
						bestNode.height = width;
						bestShortSideFit = shortSideFit;
						bestAreaFit = areaFit;
					}
				}
			}
			return {node:bestNode, score1:bestAreaFit , score2:bestShortSideFit };
		}
		
		private function FindPositionForNewNodeContactPoint(width:int, height:int, bestContactScore:int):Object{
			var bestNode:Rectangle;
//			memset(&bestNode, 0, sizeof(Rect));
			
			bestContactScore = -1;
			
			for(var i:int = 0; i < freeRectangles.length; ++i)
			{
				// Try to place the rectangle in upright (non-flipped) orientation.
				if (freeRectangles[i].width >= width && freeRectangles[i].height >= height)
				{
					var score:int = ContactPointScoreNode(freeRectangles[i].x, freeRectangles[i].y, width, height);
					if (score > bestContactScore)
					{
						bestNode.x = freeRectangles[i].x;
						bestNode.y = freeRectangles[i].y;
						bestNode.width = width;
						bestNode.height = height;
						bestContactScore = score;
					}
				}
				if (freeRectangles[i].width >= height && freeRectangles[i].height >= width)
				{
					var score:int = ContactPointScoreNode(freeRectangles[i].x, freeRectangles[i].y, height, width);
					if (score > bestContactScore)
					{
						bestNode.x = freeRectangles[i].x;
						bestNode.y = freeRectangles[i].y;
						bestNode.width = height;
						bestNode.height = width;
						bestContactScore = score;
					}
				}
			}
			return {node:bestNode, score1:bestContactScore};
		}
		
		/// @return True if the free node was split.
		private function SplitFreeNode(freeNode:Rectangle, usedNode:Rectangle):Boolean{
			// Test with SAT if the rectangles even intersect.
			if (usedNode.x >= freeNode.x + freeNode.width || usedNode.x + usedNode.width <= freeNode.x ||
				usedNode.y >= freeNode.y + freeNode.height || usedNode.y + usedNode.height <= freeNode.y)
				return false;
			
			if (usedNode.x < freeNode.x + freeNode.width && usedNode.x + usedNode.width > freeNode.x)
			{
				// New node at the top side of the used node.
				if (usedNode.y > freeNode.y && usedNode.y < freeNode.y + freeNode.height)
				{
					var newNode:Rectangle = freeNode;
					newNode.height = usedNode.y - newNode.y;
					freeRectangles.push(newNode);
				}
				
				// New node at the bottom side of the used node.
				if (usedNode.y + usedNode.height < freeNode.y + freeNode.height)
				{
					newNode = freeNode;
					newNode.y = usedNode.y + usedNode.height;
					newNode.height = freeNode.y + freeNode.height - (usedNode.y + usedNode.height);
					freeRectangles.push(newNode);
				}
			}
			
			if (usedNode.y < freeNode.y + freeNode.height && usedNode.y + usedNode.height > freeNode.y)
			{
				// New node at the left side of the used node.
				if (usedNode.x > freeNode.x && usedNode.x < freeNode.x + freeNode.width)
				{
					newNode = freeNode;
					newNode.width = usedNode.x - newNode.x;
					freeRectangles.push(newNode);
				}
				
				// New node at the right side of the used node.
				if (usedNode.x + usedNode.width < freeNode.x + freeNode.width)
				{
					newNode = freeNode;
					newNode.x = usedNode.x + usedNode.width;
					newNode.width = freeNode.x + freeNode.width - (usedNode.x + usedNode.width);
					freeRectangles.push(newNode);
				}
			}
			
			return true;
		}
		
		/// Goes through the free rectangle list and removes any redundant entries.
		private function PruneFreeList():void{
			/* 
			///  Would be nice to do something like this, to avoid a Theta(n^2) loop through each pair.
			///  But unfortunately it doesn't quite cut it, since we also want to detect containment. 
			///  Perhaps there's another way to do this faster than Theta(n^2).
			if (freeRectangles.size() > 0)
			clb::sort::QuickSort(&freeRectangles[0], freeRectangles.size(), NodeSortCmp);
			for(size_t i = 0; i < freeRectangles.size()-1; ++i)
			if (freeRectangles[i].x == freeRectangles[i+1].x &&
			freeRectangles[i].y == freeRectangles[i+1].y &&
			freeRectangles[i].width == freeRectangles[i+1].width &&
			freeRectangles[i].height == freeRectangles[i+1].height)
			{
			freeRectangles.erase(freeRectangles.begin() + i);
			--i;
			}
			*/
			
			/// Go through each pair and remove any rectangle that is redundant.
			for(var i:int = 0; i < freeRectangles.length; ++i)
				for(var j:int = i+1; j < freeRectangles.length; ++j)
				{
					if (IsContainedIn(freeRectangles[i], freeRectangles[j]))
					{
						freeRectangles.splice(i,1);
						--i;
						break;
					}
					if (IsContainedIn(freeRectangles[j], freeRectangles[i]))
					{
						freeRectangles.splice(j,1);
						--j;
					}
				}
		}
		
		public static function IsContainedIn(a:Rectangle, b:Rectangle):Boolean
		{
			return a.x >= b.x && a.y >= b.y 
				&& a.x+a.width <= b.x+b.width 
				&& a.y+a.height <= b.y+b.height;
		}
		
		/// Returns 0 if the two intervals i1 and i2 are disjoint, or the length of their overlap otherwise.
		public static function CommonIntervalLength(i1start:int, i1end:int, i2start:int, i2end:int):int
		{
			if (i1end < i2start || i2end < i1start)
				return 0;
			return Math.min(i1end, i2end) - Math.max(i1start, i2start);
		}
	}
}